//接口待优化

//字符串分割与合并
class Solution
{
public:
    vector<string> split(string s, string sp)
    {
        if (s.size() == 0) return {};
        if (s.size() < sp.size()) return {s};

        vector<string> ret;
        int sz = s.size();
        int n = sp.size();
        int start = 0;
        int pos = s.find(sp);
        while (pos != string::npos)
        {
            if (pos + sp.size()-1 == sz) return ret;
            ret.push_back(s.substr(start,pos-start));
            start = pos + n;
            pos = s.find(sp,start);
        }
        if(start < sz) ret.push_back(s.substr(start));
        return ret;
    }
    
    string merge(vector<string> arr, string sp)
    {
        if (arr.size() == 0) return "";
        if (arr.size() == 1) return arr[0];

        string ret;
        ret.reserve(arr.size()*sp.size()+arr.size()*arr[0].size());

        int n = arr.size();
        for (int i = 0; i < n; ++i)
        {
            ret += arr[i];
            if (i + 1 < n) ret += sp;
        }
        return ret;
    }
};

//1000个数中出现两次的数
int repeatNum(vector<int>& nums)
{
    char arr[1000] = { 0 };
    for (int& n : nums)
    {
        if (arr[n]) return n;
        ++arr[n];
    }
    return -1;
}

//找出最大质数
int maxPrimeNum(long long num)
{
    
    for (; num >= 2; --num)
    {
        bool flag = true;
        for (long long i = num - 1; i > 1; --i)
        {
            if (num % i == 0) 
            {
                flag = false;
                break;
            }
        }
        if (flag) return num;
    }
    return num;
}

//约瑟夫环
int JosephRing(int n,int m) 
{
    list<int> l;
    for (int i = 1; i <= n; ++i)
    {
        l.push_back(i);
    }

    auto it = l.begin();
    int cnt = 1;
    while (l.size() > 1)
    {
        if (cnt == m)
        {
            it = l.erase(it);
            cnt = 1;
        }
        else 
        {
            ++it;
            ++cnt;
        }
        if (it == l.end()) it = l.begin();
    }
    return *(l.begin());
}

//26个字母可以组成的字符串
vector<string> strCombo()
{
    vector<string> ret;
    string path;
    path.reserve(26);
    ret.reserve((26*27)/2);
    function<void()> dfs = [&]() {
        ret.push_back(path);
        if (path.size() == 26) return;

        for (char c = 'a'; c <= 'z'; ++c)
        {
            path.push_back(c);
            dfs();
            path.pop_back();
        }

    };

    //选择首字母开始组合
    for (char c = 'a';c <= 'z'; ++c)
    {
        path.push_back(c);
        dfs();
        path.pop_back();
    }

    return ret;
}